Zkouška Tancer 10. 1. 2025
Uvědtě definici kkk-degenerovaného grafu. Uvědtě příklad 333-degenerového grafu, který není 222-degenerovaný. (5 bodů)
Kolik existuje funkcí f:[n]→([n]2)f: [n] \to \binom{[n]}{2}f:[n]→(2[n]) takových, že ∀i∈[n]:i∉f(i)\forall i \in [n]: i \notin f(i)∀i∈[n]:i∈/f(i) (6 bodů)
Uvažujme ČUM P=(X,⊆)P = (X, \subseteq)P=(X,⊆), kde XXX je množina všech množin E⊆(V2)E \subseteq \binom{V}{2}E⊆(2V) rovinných grafu G=(V,E)G = (V,E)G=(V,E), pro které V=[n]V = [n]V=[n].
\newline
Neboli X={E⊆([n]2)∣X = \{E \subseteq \binom {[n]} 2 |X={E⊆(2[n])∣ graf ([n], E) je rovinný}\}}
a) Najděte řetězec v PPP s maximální velikostí a zdůvodnětě, že neexistuje řetězec s vetší delkou
b) Pro n≥3n \geq 3n≥3 najděte antiřetězec s velikostí alespoň ((n2)2)\dbinom{\binom{n}{2}}{2}(2(2n)). (existují i delší, stačí se však omezit na ((n2)2)\dbinom{\binom{n}{2}}{2}(2(2n)))
Pokud se vám nedaří vyřešit jednu z možností, vyřešte pro n=5n=5n=5. (9 bodů)
Uvědtě definici a důkaz věty o sledů (se závislosti na matici sousednosti grafu GGG) (10 bodů)
Za zkoušku bylo možné získat 30, bodů. Známkování bylo následující 1: 24-30b; 2: 20-23b; 3: 16-19b; 3−^-−: 11-15b; 4: 0-10b.
Po písemné zkoušce bylo možné si zlepšit známku 2 až 3−^-− o stupeň lepší (1 až 3) na ústní zkoušce. V případě známky 3−^-− byla zkouška povinná.
Explicitně bylo řečeno, že není možné si na ústní zkoušce zhoršit známku.
